package cs348a.data.opt;

import java.util.ArrayList;
import java.util.List;

import cs348a.data.Site;

public class NearestOptimizer extends AbstractPathOptimizer {

	@Override
	public List<Site> optimizePath(List<Site> siteList) {
		List<Site> bestList = null;
		
		double minLength = Double.MAX_VALUE;
		
		for(int i= 0; i < siteList.size(); i++) {
			List<Site> list = new ArrayList<Site>();
			double length = getPath(siteList, list, i);
			System.out.println(i + ": " + length);
			
			if(length < minLength) {
				minLength = length;
				bestList = list;
			}
		}

		return bestList;
	}

	/**
	 * Returns a single NN path in <code>list</code> and the length of the path 
	 * 
	 * @param siteList
	 * @return
	 */
	public double getPath(List<Site> siteList, List<Site> list, int firstIdx){
		// get distances between all paths
		double[][] dist = getDistances(siteList);
		int size = siteList.size();
		
		boolean[] visited = new boolean[size];
		
		int currIdx = firstIdx;
		int nextIdx = 0;
		double length = 0;
		
		for(int i = 0; i < size; i++) {
			visited[currIdx] = true;
			list.add(siteList.get(currIdx));

			double min = Double.MAX_VALUE;
			
			for(int j = 0; j < size; j++) {
				if(j != currIdx && !visited[j]) {
					if(dist[currIdx][j] < min) {
						min = dist[currIdx][j];
						nextIdx = j;
					}
				}
			}
			
			if(i != size-1) { // the last point is max
				length += min;
			}
			
			currIdx = nextIdx;
		}
		
		return length;
	}
}
